# Definition for a binary tree node.
# 稍微修改了类的定义
class TreeNode:
    def __init__(self, x, left=None, right=None):
        self.val = x
        self.left = left
        self.right = right

class Solution:
    def isLeaf(self, node: TreeNode):
        return node.left is None and node.right is None

    def minDepth(self, root: TreeNode) -> int:
        return self._minDepth([root], 1)

    def _minDepth(self, nodes, cnt):
        new_nodes = []
        for node in nodes:
            if self.isLeaf(node):
                return cnt
            if node.left:
                new_nodes.append(node.left)
            if node.right:
                new_nodes.append(node.right)
        return self._minDepth(new_nodes, cnt+1)

if __name__ == '__main__':
    s = Solution()
    tree = TreeNode(3, left=TreeNode(9), right=TreeNode(20, left=TreeNode(15), right=TreeNode(7)))
    print(s.minDepth(tree))
